package LeetCode.month01.day19;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class No3479 {
    public static void main(String[] args) {
        System.out.println(numOfUnplacedFruits(new int[]{37,38,6,5,7}, new int[]{24,28,14,25,48}));
    }
    public static int numOfUnplacedFruits(int[] fruits, int[] baskets) {
        //分块
        int n = baskets.length;
        int m = (int) Math.sqrt(n);
        int section = (n+m-1)/m;
        int[] max = new int[section];
        for (int i = 0; i < n; i++) {
            max[i/m] = Math.max(max[i/m],baskets[i]);
        }
        int count = 0;
        for (int fruit : fruits) {
            int num=1;
            int choose = 0;
            for (int i = 0; i < section; i++) {
                if(choose==0){
                    if(fruit>max[i])
                        continue;
                    max[i]=0;
                    for (int j = 0; j < m; j++) {
                        int pos = i*m+j;
                        if(pos<n){
                            if(choose==0&&fruit<=baskets[i*m+j]){
                                choose=1;
                                baskets[i*m+j]=0;
                                num=0;
                            }
                            max[i] = Math.max(max[i],baskets[i*m+j]);
                        }
                    }
                }
            }
            count+=num;
        }
        return count;

        //暴力解法
//        int num =0;
//        int len = fruits.length;
//        int len2 = baskets.length;
//        for (int i = 0; i < len; i++) {
//            for (int j = 0; j < len2; j++) {
//                if(fruits[i]<=baskets[j]){
//                    baskets[j]=0;
//                    fruits[i]=-1;
//                    break;
//                }
//            }
//            if(fruits[i]!=-1) num++;
//        }
//        return num;
    }
}
